// 题目描述
// 讨论 (367)
// 1094. 拼车
// 提示
// 中等
// 269
// 车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）
// 给定整数 capacity 和一个数组 trips ,  trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。
// 当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。
//   示例 1：
// 输入：trips = [[2,1,5],[3,3,7]], capacity = 4
// 输出：false
// 示例 2：
// 输入：trips = [[2,1,5],[3,3,7]], capacity = 5
// 输出：true
//   提示：
// 1 <= trips.length <= 1000
// trips[i].length == 3
// 1 <= numPassengersi <= 100
// 0 <= fromi < toi <= 1000
// 1 <= capacity <= 105
// 通过次数
// 77.5K
// 提交次数
// 150.2K
// 通过率
// 51.6%
// https://leetcode.cn/problems/car-pooling

/**
 * @param {number[][]} trips
 * @param {number} capacity
 * @return {boolean}
 */
var carPooling = function (trips, capacity) {
  // 根据题目限定的 trips 长度为 0~1000 构造 diff 数组
  // 差分数组模拟了车辆在每个车站上的乘客数量

  // 1. 构造 diff
  const diff = new Array(1001).fill(0)

  // 2. 操作区间
  trips.forEach(([n, start, end]) => {
    diff[start] += n
    if (end < diff.length) {
      diff[end] -= n
    }
  })

  // 3. 还原原始数组
  const res = new Array(1001).fill(0)
  res[0] = diff[0]
  for (let i = 1; i < res.length; i++) {
    res[i] = res[i - 1] + diff[i]
  }

  // 车辆再到达每个车站时，车上乘客都不应该超出容量 capacity
  return res.every(item => item <= capacity)
}

console.log(
  carPooling(
    [[2, 1, 5], [3, 3, 7]],
    5
  )
)
